package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2019-12-24 22:59
 */
public class QLint386 {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] res = new int[256];
        int j = 0;//右指针
        int c = 0;//不同字符个数
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            while (j < s.length() && c < k) {
                res[s.charAt(j)]++;
                if (res[s.charAt(j)] == 1) {
                    c++;
                }
                max = Math.max(max, j - i + 1);
                j++;
            }

            if (c == k) {
                while (j < s.length() && res[s.charAt(j)] >= 1) {
                    res[s.charAt(j)]++;
                    max = Math.max(max, j - i + 1);
                    j++;
                }
            }

            res[s.charAt(i)]--;
            if (res[s.charAt(i)] == 0) {
                c--;
            }

        }
        return max;
    }


    public int lengthOfLongestSubstringKDistinct2(String s, int k) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] res = new int[256];
        int max = 0;
        int i = 0;//左指针
        int c = 0;//不同字符的数量
        for (int j = 0; j < s.length(); j++) {
            res[s.charAt(j)]++;
            if (res[s.charAt(j)] == 1) {
                c++;
            }
            while (c > k) {
                res[s.charAt(i)]--;
                if (res[s.charAt(i)] == 0) {
                    c--;
                }
                i++;
            }
            max = Math.max(max, j - i + 1);
        }

        return max;
    }


    public static void main(String[] args) {
        System.out.println(new QLint386().lengthOfLongestSubstringKDistinct2("eqgkcwGFvjjmxutystqdfhuMblWbylgjxsxgnoh", 16));
    }
}
